package m202401.d11;

import m202401.d10.Q222;

import java.util.Arrays;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/1/11 17:07
 */
//106. 从中序与后序遍历序列构造二叉树
public class Q106 {

    public static void main(String[] args) {
        new Q106().buildTree(new int[]{9, 3, 15, 20, 7}, new int[]{9, 15, 7, 20, 3});
    }

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return buildTree(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }

    public TreeNode buildTree(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {
        if (inStart == inEnd || postStart == postEnd) {
            return null;
        }
        TreeNode node = new TreeNode(postorder[postEnd - 1]);
        int index = findIndex(node.val, inorder, inStart, inEnd);
        node.left = buildTree(inorder, inStart, index, postorder, postStart, postStart + (index - inStart));
        node.right = buildTree(inorder, index + 1, inEnd, postorder, postStart + (index - inStart), postEnd - 1);
        return node;
    }

    public int findIndex(int target, int[] inorder, int inStart, int inEnd) {
        for (int i = inStart; i < inEnd; i++) {
            if (inorder[i] == target) {
                return i;
            }
        }
        return -1;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
